package main.LeetCode75.Level1;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class Day1_Day5 {
    public static void main(String[] args) {
        System.out.println("**************************Day1**************************");
        System.out.println("Question1480：一维数组的动态和");
        System.out.println("Question742：寻找数组的中心下标");
        System.out.println("**************************Day2**************************");
        System.out.println("Question205：同构字符串");
        System.out.println("Question392：判断子序列");
        System.out.println("**************************Day3**************************");
        System.out.println("Question21：合并两个有序链表");
        System.out.println("Question206：反转链表");
        System.out.println("**************************Day4**************************");
        System.out.println("Question876：链表的中间结点");
        System.out.println("Question142：环形链表 II");
        System.out.println("**************************Day5**************************");
        System.out.println("Question121：买卖股票的最佳时机");
        System.out.println("Question409：最长回文串");
    }
}

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

class Question1480{
    public int[] runningSum(int[] nums) {
        int[] result=new int[nums.length];
        int lastSum=0;
        for (int i=0;i< nums.length;i++){
            result[i]=lastSum+nums[i];
            lastSum+=nums[i];
        }
        return result;
    }
}

class Question742{
    public int pivotIndex(int[] nums) {
        int middleIndex=-1;
        int[] leftSum=new int[nums.length],rightSum=new int[nums.length];
        if (nums.length!=1){
            for (int i=0;i< nums.length;i++){
                if (i==0) leftSum[i]=nums[i];
                else leftSum[i]=leftSum[i-1]+nums[i];
            }
            for (int j= nums.length-1;j>=0;j--){
                if (j== nums.length-1) rightSum[j]=nums[j];
                else rightSum[j]=rightSum[j+1]+nums[j];
            }
            for (int i=0;i< nums.length;i++){
                if (i==0&&0==rightSum[1]){
                    middleIndex=0;
                    break;
                }else if (i== nums.length-1&&leftSum[nums.length-2]==0){
                    middleIndex= nums.length-1;
                    break;
                }else if (i!=0&&i!= nums.length-1&&leftSum[i-1]==rightSum[i+1]){
                    middleIndex=i;
                    break;
                }
            }
        }else if (nums.length==1) middleIndex=0;
        return middleIndex;
    }
}

class Question205{
    public boolean isIsomorphic(String s, String t) {
        Map<Character, Character> s2t = new HashMap<Character, Character>();//建立2个map，两个字符串两相对应
        Map<Character, Character> t2s = new HashMap<Character, Character>();
        int len = s.length();
        for (int i = 0; i < len; ++i) {
            char x = s.charAt(i), y = t.charAt(i);
            if ((s2t.containsKey(x) && s2t.get(x) != y) || (t2s.containsKey(y) && t2s.get(y) != x)) {
                return false;
            }
            s2t.put(x, y);
            t2s.put(y, x);
        }
        return true;
    }
}

class Question392{
    public boolean isSubsequence(String s, String t) {//双指针
        if (s.length() == 0) return true;
        for (int i = 0, j = 0; j < t.length(); j++) {
            if (s.charAt(i) == t.charAt(j)) {
                if (++i == s.length())
                    return true;
            }
        }
        return false;
    }
}

class Question21{
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode prehead = new ListNode(-1);
        ListNode prev = prehead;
        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                prev.next = list1;
                list1 = list1.next;
            } else {
                prev.next = list2;
                list2 = list2.next;
            }
            prev = prev.next;
        }
        prev.next = list1 == null ? list2 : list1;
        return prehead.next;
    }
}

class Question206{
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
}

class Question876{
    public ListNode middleNode(ListNode head) {
        ListNode fast=head,slow=head;
        if (head.next==null) return head;
        else if (head.next.next==null) return head.next;
        while (fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        return slow;
    }
}

class Question142{
    public ListNode detectCycle(ListNode head) {
        if (head==null||head.next==null) return null;
        ListNode slow=head,fast=head;
        do {
            if (fast!=null&&fast.next!=null) {
                fast = fast.next.next;
                slow = slow.next;
            }else return null;
        }while (fast!=slow);//判断存在环
        if (fast!=null) {//填补快慢指针步差
            slow = head;
            while (slow!=fast){
                slow=slow.next;
                fast=fast.next;
            }
        }
        return fast;
    }
}

class Question121{
    public int maxProfit(int[] prices) {
        int minprice = Integer.MAX_VALUE;
        int maxprofit = 0;
        for (int i = 0; i < prices.length; i++) {
            if (prices[i] < minprice) {
                minprice = prices[i];
            } else if (prices[i] - minprice > maxprofit) {
                maxprofit = prices[i] - minprice;
            }
        }
        return maxprofit;
    }
}

class Question409{
    public int longestPalindrome(String s) {//最长回文串为，所有偶数个字符个数相加再加上最大的奇数字符个数
        int[] charCount=new int[123];
        int length=0;
        for (char c:s.toCharArray()) charCount[c]++;
        Arrays.sort(charCount);
        for (int v:charCount){
            length+=v/2*2;
            if (v%2==1&&length%2==0) length++;
        }
        return length;
    }
}

